#define _CRT_SECURE_NO_WARNINGS 1 
#include <stdio.h>
#include <malloc.h>
//操作算法中用到的预定义的常量和类型
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

//Status是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;

//顺序表存储结构
#define MAXSIZE 100   //顺序表可能达到的最大长度
typedef struct SL
{
	ElemType* elem;   //存储空间的基地址
	int length;       //当前长度
}SqList;                  //顺序表的结构类型为SqList

//函数声明
Status InitList(SqList* L);//初始化 - 构造一个空的线性表L
Status DestroyList(SqList* L);//销毁
Status ClearList(SqList* L);//置空
Status ListEmpty(SqList* L);//判空(若线性表L为空表,则返回TRUE，否则返回FALSE)
Status ListLength(SqList* L);//返回L中数据元素的个数
ElemType GetElem(SqList* L, int i, ElemType e);//用e返回L中第i个数据元素的值.(初始条件:线性表已存在,且1 ≤ i ≤ ListLength(L))
Status LocateElem(SqList* L, ElemType e);//返回L中第1个与e相同的允许在L中的位置。若这样的元素不存在，则返回值为0
ElemType PriorElem(SqList* L, ElemType cur_e, ElemType* p_pre_e);//若cur_e是L的数据元素,且不是第一个，则用pre_e返回其前驱,否则操作失败,pre_e无定义
ElemType NextElem(SqList* L, ElemType cur_e, ElemType* p_next_e);//若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义
void ListInsert(SqList* L, int i, ElemType e);//在L中第i个位置之前插入新的数据元素e，L的长度+1
void ListDelete(SqList* L, int i);//删除L的第i个元素，L的长度-1
void TraverseList(const SqList* L);//对线性表L进行遍历，在遍历过程中对L的每个结点访问一次


int main(void)
{
	//定义顺序表L
	SqList L;

	int i = 0;
	char e = 0,	cur_e = 0,	pre_e = 0,	next_e = 0;

	//初始化 - 构造一个空的线性表L
	InitList(&L);
	

	//添加元素
	ListInsert(&L, 1, 'a');
	ListInsert(&L, 2, 'b');
	ListInsert(&L, 3, 'c');
	ListInsert(&L, 4, 'd');
	ListInsert(&L, 5, 'e');
	ListInsert(&L, 6, 'f');
	ListInsert(&L, 7, 'g');
	ListInsert(&L, 8, 'h');
	ListInsert(&L, 9, 'i');
	ListInsert(&L, 10, 'j');
	ListInsert(&L, 11, 'k');
	//遍历
	TraverseList(&L);
	//显示L中数据元素的个数
	printf("此时L中数据元素的个数为：%d\n", ListLength(&L));
	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n");


	//用e返回L中第i个数据元素的值.
	//初始条件:线性表已存在,且1 ≤ i ≤ ListLength(L)
	for (i = 0; i < L.length; i++)
	{
		e = L.elem[i];
		printf("L中的第 %d 个元素为：%c\n", i+1, e);
	}
	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n");


	//返回L中第1个与e相同的允许在L中的位置。若这样的元素不存在，则返回值为0
	e = 'k';
	if (i = LocateElem(&L, e))
	{
		printf("L中与\"e = %c\"相同的元素存在，位置：L.elem[%d] = %c\n", e, i, L.elem[i]);
	}
	else
	{
		printf("L中不存在与e相同的元素\n");
	}
	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n");


	//若cur_e是L的数据元素,且不是第一个，则用pre_e返回其前驱,否则操作失败,pre_e无定义
	cur_e = L.elem[0];   //cur_e是L的第一个数据数据元素
	if (PriorElem(&L, cur_e, &pre_e))
	{
		printf("cur_e = \'%c\'是L的数据元素(且不是第一个)，cur_e的前驱元素为 pre_e = \'%c\'\n", cur_e, pre_e);
	}
	else
	{
		printf("操作失败, pre_e 无定义\n");
	}
	//cur_e不是L的第一个元素
	for (i = 1; i < L.length; i++)
	{
		cur_e = L.elem[i];
		if (PriorElem(&L, cur_e, &pre_e))
		{
			printf("cur_e = \'%c\'是L的数据元素(且不是第一个)，cur_e的前驱元素为 pre_e = \'%c\'\n", cur_e, pre_e);
		}
		else
		{
			printf("操作失败, pre_e 无定义\n");
		}
	}
	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n");


	//若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义
	cur_e = L.elem[L.length-1];   //cur_e是L的最后一个数据数据元素
	if (NextElem(&L, cur_e, &next_e))
	{
		printf("cur_e = \'%c\'是L的数据元素(且不是最后一个)，cur_e的后继元素为 pre_e = \'%c\'\n", cur_e, next_e);
	}
	else
	{
		printf("操作失败, next_e 无定义\n");
	}
	//cur_e不是L的最后一个元素
	for (i = 0; i < L.length - 1; i++)
	{
		cur_e = L.elem[i];
		if (NextElem(&L, cur_e, &next_e))   //遍历的结束点 应小于 线性表总长度 - 1(即ListLength - 1)
		{
			printf("cur_e = \'%c\'是L的数据元素(且不是最后一个)，cur_e的后继元素为 pre_e = \'%c\'\n", cur_e, next_e);
		}
		else
		{
			printf("操作失败, next_e 无定义\n");
		}
	}
	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n");


	//在L中第i个位置之前插入新的数据元素e，L的长度+1
	ListInsert(&L, 2, 'A');
	ListInsert(&L, 4, 'A');
	ListInsert(&L, 6, 'A');
	ListInsert(&L, 8, 'A');
	ListInsert(&L, 10, 'A');
	ListInsert(&L, 12, 'A');
	ListInsert(&L, 14, 'A');
	ListInsert(&L, 16, 'A');
	ListInsert(&L, 18, 'A');
	ListInsert(&L, 20, 'A');
	//遍历
	TraverseList(&L);
	//显示L中数据元素的个数
	printf("此时L中数据元素的个数为：%d\n", ListLength(&L));
	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n");


	//删除L的第i个元素，L的长度-1
	ListDelete(&L, 2);
	ListDelete(&L, 3);
	ListDelete(&L, 4);
	ListDelete(&L, 5);
	ListDelete(&L, 6);
	ListDelete(&L, 7);
	ListDelete(&L, 8);
	ListDelete(&L, 9);
	ListDelete(&L, 10);
	ListDelete(&L, 11);
	//遍历
	TraverseList(&L);
	//显示L中数据元素的个数
	printf("此时L中数据元素的个数为：%d\n", ListLength(&L));
	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n");


	//置空
	ClearList(&L);
	if (ListEmpty(&L))
	{
		printf("线性表L为空表!\n");
	}
	else
	{
		printf("线性表L不为空\n");
	}
	//遍历
	TraverseList(&L);
	//显示L中数据元素的个数
	printf("此时L中数据元素的个数为：%d\n", ListLength(&L));
	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n");


	//销毁
	DestroyList(&L);



	return 0;
}

//初始化 - 构造一个空的线性表L
Status InitList(SqList* L)
{
	L->elem = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);   //为顺序表分配一个大小为MAXSIZE的数组空间
	if (!L->elem)
	{
		printf("内存分配失败!\n");
		exit(OVERFLOW);   //存储分配失败退出 
	}
	L->length = 0;   //空表长度为0
	return OK;
}

//销毁
Status DestroyList(SqList* L)
{
		free(L->elem);
		L->elem = NULL;
		L->length = 0;
		printf("顺序表已销毁!");
		return OK;
}

//置空
Status ClearList(SqList* L)
{
	if (ListEmpty(L))   //置空进行判空判断
	{
		printf("线性表L已为空表，无需置空.");
		return FALSE;   //线性表L置空前已为空表
	}
	else
	{
		free(L->elem);
		L->elem = NULL;
		L->length = 0;
		return TRUE;   //线性表置空后
	}
}

//判空
//若线性表L为空表,则返回TRUE，否则返回FALSE
Status ListEmpty(SqList* L)
{

	if (0 == L->length)
	{
		return TRUE;   //线性表为空
	}
	else
	{
		return FALSE;   //线性表非空
	}
}

//返回L中数据元素的个数
Status ListLength(SqList* L)
{
	return L->length;
}

//用e返回L中第i个数据元素的值.
//初始条件:线性表已存在,且1 ≤ i ≤ ListLength(L)
ElemType GetElem(SqList* L, int i, ElemType e)   
{
	if (i<1 || i>L->length)
	{
		return ERROR;
	}
	e = *(L->elem + i - 1);
	return OK;
}

//返回L中第1个与e相同的允许在L中的位置。若这样的元素不存在，则返回值为0
Status LocateElem(SqList* L, ElemType e)
{
	int i = 0;
	for (i = 0; i < L->length; i++)
	{
		if (*(L->elem + i) == e)
		{
			return i;
		}
	}
	return 0;   //该语句位于for语句之外
}

//若cur_e是L的数据元素,且不是第一个，则用pre_e返回其前驱,否则操作失败,pre_e无定义
ElemType PriorElem(SqList* L, ElemType cur_e, ElemType* p_pre_e)
{
	int i = 0;

	if (cur_e == L->elem[0])   //当cur_e是L的第一个元素时
	{
		return ERROR;
	}
	for (i = 1; i < L->length; i++)   //从线性表的第2个元素开始遍历
	{
		if (*(L->elem + i) == cur_e)
		{
			*p_pre_e = *(L->elem + i - 1);
			return *p_pre_e;
		}
	}
	return ERROR;
}

//若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义
ElemType NextElem(SqList* L, ElemType cur_e, ElemType* p_next_e)
{
	int i = 0;

	if (cur_e == L->elem[L->length - 1])   //当cur_e是L的最后一个元素时
	{
		return ERROR;
	}
	for (i = 0; i < L->length - 1; i++)   //遍历的结束点 应小于 线性表总长度 - 1(即ListLength - 1)
	{
		if (*(L->elem + i) == cur_e)
		{
			*p_next_e = *(L->elem + i + 1);
			return *p_next_e;
		}
	}
	return ERROR;
}

//在L中第i个位置之前插入新的数据元素e，L的长度+1
void ListInsert(SqList* L, int i, ElemType e)
{
	int j = 0;
	if (L->length == 0)   //用于线性表为空
	{
		L->length++;
		*(L->elem + i - 1) = e;
	}
	else   //用于线性表不为空
	{
		L->length++;
		if (i<1 || i>L->length + 1)
		{
			return ERROR;
		}
		else
		{
			for (j = L->length - 1; j > i - 1; j--)
			{
				*(L->elem + j) = *(L->elem + j - 1);
			}
			*(L->elem + i - 1) = e;
		}
	}
}

//删除L的第i个元素，L的长度-1
void ListDelete(SqList* L, int i)
{
	int j = 0;
	if (i<1 || i>L->length)
	{
		return ERROR;
	}
	else
	{
		if (i == L->length)
		{
			*(L->elem + i - 1) = 0;
			L->length--;
		}
		else
		{
			for (j = i - 1; j < L->length; j++)
			{
				*(L->elem + j) = *(L->elem + j + 1);
			}
			L->length--;
		}
	}
}

//对线性表L进行遍历，在遍历过程中对L的每个结点访问一次
void TraverseList(const SqList* L)
{
	int i = 0;
	for (i = 0; i < L->length; i++)
	{
		printf("%c ", *(L->elem + i));
	}
	printf("\n");
}